{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Second Minimum Time to Reach Destination"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #graph #shortest-path"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #图 #最短路"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: secondMinimum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #到达目的地的第二短时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>城市用一个 <strong>双向连通</strong> 图表示，图中有 <code>n</code> 个节点，从 <code>1</code> 到 <code>n</code> 编号（包含 <code>1</code> 和 <code>n</code>）。图中的边用一个二维整数数组 <code>edges</code> 表示，其中每个 <code>edges[i] = [u<sub>i</sub>, v<sub>i</sub>]</code>&nbsp;表示一条节点&nbsp;<code>u<sub>i</sub></code> 和节点&nbsp;<code>v<sub>i</sub></code> 之间的双向连通边。每组节点对由 <strong>最多一条</strong> 边连通，顶点不存在连接到自身的边。穿过任意一条边的时间是 <code>time</code>&nbsp;分钟。</p>\n",
    "\n",
    "<p>每个节点都有一个交通信号灯，每 <code>change</code> 分钟改变一次，从绿色变成红色，再由红色变成绿色，循环往复。所有信号灯都&nbsp;<strong>同时</strong> 改变。你可以在 <strong>任何时候</strong> 进入某个节点，但是 <strong>只能</strong> 在节点&nbsp;<strong>信号灯是绿色时</strong> 才能离开。如果信号灯是&nbsp; <strong>绿色</strong> ，你 <strong>不能</strong> 在节点等待，必须离开。</p>\n",
    "\n",
    "<p><strong>第二小的值</strong> 是&nbsp;<strong>严格大于</strong> 最小值的所有值中最小的值。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>[2, 3, 4]</code> 中第二小的值是 <code>3</code> ，而 <code>[2, 2, 4]</code> 中第二小的值是 <code>4</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你 <code>n</code>、<code>edges</code>、<code>time</code> 和 <code>change</code> ，返回从节点 <code>1</code> 到节点 <code>n</code> 需要的 <strong>第二短时间</strong> 。</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>你可以 <strong>任意次</strong> 穿过任意顶点，<strong>包括</strong> <code>1</code> 和 <code>n</code> 。</li>\n",
    "\t<li>你可以假设在 <strong>启程时</strong> ，所有信号灯刚刚变成 <strong>绿色</strong> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/09/29/e1.png\" style=\"width: 200px; height: 250px;\" />        <img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/09/29/e2.png\" style=\"width: 200px; height: 250px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5, edges = [[1,2],[1,3],[1,4],[3,4],[4,5]], time = 3, change = 5\n",
    "<strong>输出：</strong>13\n",
    "<strong>解释：</strong>\n",
    "上面的左图展现了给出的城市交通图。\n",
    "右图中的蓝色路径是最短时间路径。\n",
    "花费的时间是：\n",
    "- 从节点 1 开始，总花费时间=0\n",
    "- 1 -&gt; 4：3 分钟，总花费时间=3\n",
    "- 4 -&gt; 5：3 分钟，总花费时间=6\n",
    "因此需要的最小时间是 6 分钟。\n",
    "\n",
    "右图中的红色路径是第二短时间路径。\n",
    "- 从节点 1 开始，总花费时间=0\n",
    "- 1 -&gt; 3：3 分钟，总花费时间=3\n",
    "- 3 -&gt; 4：3 分钟，总花费时间=6\n",
    "- 在节点 4 等待 4 分钟，总花费时间=10\n",
    "- 4 -&gt; 5：3 分钟，总花费时间=13\n",
    "因此第二短时间是 13 分钟。      \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/09/29/eg2.png\" style=\"width: 225px; height: 50px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2, edges = [[1,2]], time = 3, change = 2\n",
    "<strong>输出：</strong>11\n",
    "<strong>解释：</strong>\n",
    "最短时间路径是 1 -&gt; 2 ，总花费时间 = 3 分钟\n",
    "第二短时间路径是 1 -&gt; 2 -&gt; 1 -&gt; 2 ，总花费时间 = 11 分钟</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>n - 1 &lt;= edges.length &lt;= min(2 * 10<sup>4</sup>, n * (n - 1) / 2)</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= u<sub>i</sub>, v<sub>i</sub> &lt;= n</code></li>\n",
    "\t<li><code>u<sub>i</sub> != v<sub>i</sub></code></li>\n",
    "\t<li>不含重复边</li>\n",
    "\t<li>每个节点都可以从其他节点直接或者间接到达</li>\n",
    "\t<li><code>1 &lt;= time, change &lt;= 10<sup>3</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [second-minimum-time-to-reach-destination](https://leetcode.cn/problems/second-minimum-time-to-reach-destination/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [second-minimum-time-to-reach-destination](https://leetcode.cn/problems/second-minimum-time-to-reach-destination/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n[[1,2],[1,3],[1,4],[3,4],[4,5]]\\n3\\n5', '2\\n[[1,2]]\\n3\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        dic = [[] for _ in range(n + 1)]\n",
    "        dist = [0] * (n + 1)\n",
    "        visit = [0] * (n + 1)\n",
    "        for e in edges:\n",
    "            dic[e[0]].append(e[1])\n",
    "            dic[e[1]].append(e[0])\n",
    "        q = deque()\n",
    "        q.append([1, 0])\n",
    "        visit[1] = 1\n",
    "        while q:\n",
    "            curr, t = q.popleft()\n",
    "            nChange = t // change\n",
    "            if nChange % 2 == 1:\n",
    "                t = nChange * change + change\n",
    "            t += time\n",
    "            for i in dic[curr]:\n",
    "                # 厉害的剪枝：因为t是非递减的，不同距离访问超过2次的节点，不可能是第二最小值经过的节点\n",
    "                if visit[i] < 2 and dist[i] != t:\n",
    "                    dist[i] = t\n",
    "                    visit[i] += 1\n",
    "                    if visit[i] == 2 and i == n:\n",
    "                        return t\n",
    "                    q.append([i, t])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        dic = [[] for _ in range(n + 1)]\n",
    "        dist = [0] * (n + 1)\n",
    "        visit = [0] * (n + 1)\n",
    "        for e in edges:\n",
    "            dic[e[0]].append(e[1])\n",
    "            dic[e[1]].append(e[0])\n",
    "        q = deque()\n",
    "        q.append([1, 0])\n",
    "        visit[1] = 1\n",
    "        while q:\n",
    "            curr, t = q.popleft()\n",
    "            nChange = t // change\n",
    "            if nChange % 2 == 1:\n",
    "                t = nChange * change + change\n",
    "            t += time\n",
    "            for i in dic[curr]:\n",
    "                # 厉害的剪枝：因为t是非递减的，不同距离访问超过2次的节点，不可能是第二最小值经过的节点\n",
    "                if visit[i] < 2 and dist[i] != t:\n",
    "                    dist[i] = t\n",
    "                    visit[i] += 1\n",
    "                    if visit[i] == 2 and i == n:\n",
    "                        return t\n",
    "                    q.append([i, t])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        dic = [[] for _ in range(n + 1)]\n",
    "        dist = [0] * (n + 1)\n",
    "        visit = [0] * (n + 1)\n",
    "        for e in edges:\n",
    "            dic[e[0]].append(e[1])\n",
    "            dic[e[1]].append(e[0])\n",
    "        q = deque()\n",
    "        q.append([1, 0])\n",
    "        visit[1] = 1\n",
    "        while q:\n",
    "            curr, t = q.popleft()\n",
    "            nChange = t // change\n",
    "            if nChange % 2 == 1:\n",
    "                t = nChange * change + change\n",
    "            t += time\n",
    "            for i in dic[curr]:\n",
    "                if visit[i] < 2 and dist[i] != t:\n",
    "                    dist[i] = t\n",
    "                    visit[i] += 1\n",
    "                    if visit[i] == 2 and i == n:\n",
    "                        return t\n",
    "                    q.append([i, t])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        # 1. O(V+E) build adjacency list of undirected graph\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "\n",
    "        # 2. O(V+E) run BFS\n",
    "        dist = self.bfs(0, g)\n",
    "\n",
    "        ans = 0 \n",
    "        for i in range(dist[n-1]):\n",
    "            q, r = divmod(ans, change)\n",
    "            if q % 2:   # red\n",
    "                wait = change - r \n",
    "            else:       # green\n",
    "                wait = 0\n",
    "            ans += time + wait \n",
    "\n",
    "        return ans \n",
    "    \n",
    "\n",
    "    def bfs(self, start: int, g: List[List[int]]) -> List[int]:\n",
    "        n = len(g)\n",
    "        dist1 = [math.inf] * n     # shortest path\n",
    "        dist2 = [math.inf] * n     # second shortest path\n",
    "        dist1[start] = 0 \n",
    "        \n",
    "        depth = 0\n",
    "        queue = deque([start]) \n",
    "        while queue:\n",
    "            depth += 1\n",
    "            for _ in range(len(queue)):\n",
    "                u = queue.popleft()\n",
    "\n",
    "                for v in g[u]:\n",
    "                    if dist1[v] > depth:\n",
    "                        dist1[v] = depth\n",
    "                        queue.append(v)\n",
    "\n",
    "                    elif dist1[v] < depth < dist2[v]:\n",
    "                        dist2[v] = depth \n",
    "                        queue.append(v)\n",
    "        return dist2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        q = deque([(1, 0)])\n",
    "        m = defaultdict(list)\n",
    "        for f, t in edges:\n",
    "            m[f].append(t)\n",
    "            m[t].append(f)\n",
    "\n",
    "        minl, l = inf, inf\n",
    "        dist = [[inf] * 2 for _ in range(n + 1)]\n",
    "        dist[1][0] = 0\n",
    "        while dist[n][1] == inf:\n",
    "            p, s = q.popleft()\n",
    "            for np in m[p]:\n",
    "                if s + 1 < dist[np][0]:\n",
    "                    dist[np][0] = s + 1\n",
    "                    q.append((np, s + 1))\n",
    "                elif dist[np][0] < s + 1 < dist[np][1]:\n",
    "                    dist[np][1] = s + 1\n",
    "                    q.append((np, s + 1))\n",
    "        \n",
    "        t = 0\n",
    "        for _ in range(dist[n][1]):\n",
    "            if (t // change) % 2 == 0:\n",
    "                t += time\n",
    "            else:\n",
    "                t = t // change * change + change + time\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        q = deque([(1, 0)])\n",
    "        dis = [[inf] * 2 for _ in range(n + 1)]\n",
    "        dis[1][0] = 0\n",
    "\n",
    "        while q:\n",
    "            node, d = q.popleft()\n",
    "            for ch in g[node]:\n",
    "                if d + 1 < dis[ch][1]:\n",
    "                    if d + 1 < dis[ch][0]:\n",
    "                        dis[ch] = [d + 1, dis[ch][0]]\n",
    "                    elif d + 1 == dis[ch][0]:\n",
    "                        continue\n",
    "                    else:\n",
    "                        dis[ch][1] = d + 1\n",
    "                    q.append((ch, d + 1))\n",
    "\n",
    "        l, r = change, 2 * change\n",
    "        ans = 0\n",
    "        cnt = dis[n][1]\n",
    "        for i in range(cnt):\n",
    "            ans += time\n",
    "            while ans >= r:\n",
    "                r += 2 * change\n",
    "            l = r - change\n",
    "            if l <= ans <= r and i != cnt - 1:\n",
    "                ans = r\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        dist = [[inf] * 2 for _ in range(n + 1)]\n",
    "        dist[1][0] = 0\n",
    "        q = deque([(1, 0)])\n",
    "        while dist[n][1] == inf:\n",
    "            ver, d = q.popleft()\n",
    "            d += 1\n",
    "            for node in graph[ver]:\n",
    "                if d < dist[node][0]:\n",
    "                    dist[node][0] = d\n",
    "                    q.append((node, d))\n",
    "                if dist[node][0] < d < dist[node][1]:\n",
    "                    dist[node][1] = d\n",
    "                    q.append((node, d))\n",
    "        ans = 0\n",
    "        for _ in range(dist[n][1]):\n",
    "            if ans % (2 * change) >= change:\n",
    "                ans += change * 2 - ans % (2 * change)\n",
    "            ans += time\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "        q = [(0, n)]\n",
    "        dis = [inf] * (n + 1)\n",
    "        dis[n] = 0\n",
    "        while q:\n",
    "            d, node = heapq.heappop(q)\n",
    "            if d > dis[node]:\n",
    "                continue\n",
    "\n",
    "            for ch in g[node]:\n",
    "                if d + 1 < dis[ch]:\n",
    "                    dis[ch] = d + 1\n",
    "                    heapq.heappush(q, (dis[ch], ch))\n",
    "\n",
    "        def check(num):\n",
    "            l, r = change, 2 * change\n",
    "            res = 0\n",
    "            for i in range(num):\n",
    "                res += time\n",
    "                while res >= r:\n",
    "                    r += 2 * change\n",
    "                l = r - change\n",
    "                if l <= res <= r and i != num - 1:\n",
    "                    res = r\n",
    "            return res\n",
    "\n",
    "        mi = dis[1] + 1\n",
    "\n",
    "        q = deque([(1, 0)])\n",
    "        seen = set([(1, 0)])\n",
    "        while q:\n",
    "            node, d = q.popleft()\n",
    "            if any(d + 1 + dis[ch] == mi for ch in g[node]):\n",
    "                return check(mi)\n",
    "            \n",
    "            for ch in g[node]:\n",
    "                if ch not in seen:\n",
    "                    seen.add(ch)\n",
    "                    q.append((ch, d + 1))\n",
    "\n",
    "        return check(mi + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: [], time: int, change: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)\n",
    "\n",
    "        def next(now):\n",
    "            if (now // change) % 2 == 1:\n",
    "                return (now // change + 1) * change + time\n",
    "            return now + time\n",
    "\n",
    "        first = [inf] * n\n",
    "        second = [inf] * n\n",
    "        first[0] = 0\n",
    "        now = 0\n",
    "\n",
    "        q = deque([0])\n",
    "        while q:\n",
    "            now = next(now)\n",
    "            for i in range(len(q)):\n",
    "                x = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if first[y] == inf:\n",
    "                        first[y] = now\n",
    "\n",
    "                    elif now > first[y] and second[y] == inf:\n",
    "                        second[y] = now\n",
    "                    else:\n",
    "                        continue\n",
    "                    q.append(y)\n",
    "\n",
    "            if second[n - 1] < inf:\n",
    "                return second[n - 1]\n",
    "\n",
    "\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: [], time: int, change: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)\n",
    "\n",
    "        def next(now):\n",
    "            if (now // change) % 2 == 1:\n",
    "                return (now // change + 1) * change + time\n",
    "            return now + time\n",
    "\n",
    "        first = [inf] * n\n",
    "        second = [inf] * n\n",
    "        first[0] = 0\n",
    "        now = 0\n",
    "\n",
    "        q = deque([0])\n",
    "        while q:\n",
    "            now = next(now)\n",
    "            for i in range(len(q)):\n",
    "                x = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if first[y] == inf:\n",
    "                        first[y] = now\n",
    "\n",
    "                    elif now > first[y] and second[y] == inf:\n",
    "                        second[y] = now\n",
    "                    else:\n",
    "                        continue\n",
    "                    q.append(y)\n",
    "\n",
    "            if second[n - 1] < inf:\n",
    "                return second[n - 1]\n",
    "\n",
    "\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        line = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            line[u].append(v)\n",
    "            line[v].append(u)\n",
    "        dis = [[inf]*2 for _ in range(n+1)]\n",
    "        dis[1][0] = 0\n",
    "        q = deque([(1,0)])\n",
    "        while dis[n][1] == inf:\n",
    "            u,d = q.popleft()\n",
    "            d += 1\n",
    "            for v in line[u]:\n",
    "                if d < dis[v][0]:\n",
    "                    dis[v][1] = dis[v][0]\n",
    "                    dis[v][0] = d\n",
    "                    q.append((v,d))\n",
    "                elif dis[v][0] < d < dis[v][1]:\n",
    "                    dis[v][1] = d\n",
    "                    q.append((v,d))\n",
    "        t = 0\n",
    "        for k in range(dis[n][1]-1):\n",
    "            t += time\n",
    "            if (t//change+1)%2 == 0:\n",
    "                t = (t//change+1)*change\n",
    "        return t+time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        graph = [[] for _ in range(n+1)]\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "\n",
    "        distance = [[float(\"inf\")] * 2 for _ in range(n+1)]\n",
    "        distance[1][0] = 0\n",
    "        q = deque([(1, 0)])\n",
    "        while distance[n][1] == float(\"inf\"):\n",
    "            p = q.popleft()\n",
    "            for y in graph[p[0]]:\n",
    "                d = p[1] + 1\n",
    "                if d < distance[y][0]:\n",
    "                    distance[y][0] = d\n",
    "                    q.append((y, d))\n",
    "                elif distance[y][0] < d < distance[y][1]:\n",
    "                    distance[y][1] = d\n",
    "                    q.append((y, d))\n",
    "        ans = 0\n",
    "        for _ in range(distance[n][1]):\n",
    "            if ans % (change * 2) >= change:\n",
    "                ans += change * 2 - ans % (change * 2)\n",
    "            ans += time\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "\n",
    "        graph = defaultdict(list)\n",
    "        \n",
    "        for u , v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "\n",
    "        dist = [[inf,inf] for _ in range(n+1)]\n",
    "        path = 2 * change\n",
    "\n",
    "        queue = deque([(1,0)])\n",
    "        while queue:\n",
    "            node , cost = queue.popleft()\n",
    "            n_cost = 0\n",
    "            if cost % path < change:\n",
    "                n_cost = cost + time\n",
    "            else:\n",
    "                n_cost = (cost//path)*path + path + time\n",
    "            for nxt in graph[node]:\n",
    "                if dist[nxt][0] > n_cost:\n",
    "                    dist[nxt][1] = dist[nxt][0]\n",
    "                    dist[nxt][0] = n_cost\n",
    "                    queue.append((nxt,n_cost))\n",
    "                elif dist[nxt][1] > n_cost > dist[nxt][0]:\n",
    "                    dist[nxt][1] = n_cost\n",
    "                    queue.append((nxt,n_cost))\n",
    "\n",
    "        return dist[n][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        graph = [[] for _ in range(n + 1)]\n",
    "        for e in edges:\n",
    "            x, y = e[0], e[1]\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "\n",
    "        # dist[i][0] 表示从 1 到 i 的最短路长度，dist[i][1] 表示从 1 到 i 的严格次短路长度\n",
    "        dist = [[float('inf')] * 2 for _ in range(n + 1)]\n",
    "        dist[1][0] = 0\n",
    "        q = deque([(1, 0)])\n",
    "        while dist[n][1] == float('inf'):\n",
    "            p = q.popleft()\n",
    "            for y in graph[p[0]]:\n",
    "                d = p[1] + 1\n",
    "                if d < dist[y][0]:\n",
    "                    dist[y][0] = d\n",
    "                    q.append((y, d))\n",
    "                elif dist[y][0] < d < dist[y][1]:\n",
    "                    dist[y][1] = d\n",
    "                    q.append((y, d))\n",
    "\n",
    "        ans = 0\n",
    "        for _ in range(dist[n][1]):\n",
    "            if ans % (change * 2) >= change:\n",
    "                ans += change * 2 - ans % (change * 2)\n",
    "            ans += time\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache,lru_cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "import sys\n",
    "\n",
    "# sys.setrecursionlimit(100000)\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        dist = [[inf] * 2 for _ in range(n + 1)]\n",
    "        dist[1][0] = 0\n",
    "        q= PriorityQueue()\n",
    "        q.put((0,1))\n",
    "        while not q.empty():\n",
    "            t,u = q.get()\n",
    "            for v in g[u]:\n",
    "                d = t + 1\n",
    "                if d < dist[v][0]:\n",
    "                    dist[v][0] = d\n",
    "                    q.put((d, v))\n",
    "                elif dist[v][0] < d < dist[v][1]:\n",
    "                    dist[v][1] = d\n",
    "                    q.put((d, v))\n",
    "        ans = 0\n",
    "        for _ in range(dist[-1][-1]):\n",
    "            if ans % (change * 2) >= change:\n",
    "                ans += change * 2 - ans % (change * 2)\n",
    "            ans += time\n",
    "        return ans\n",
    "\n",
    "# end-------------------------------------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        graph = [[] for _ in range(n + 1)]\n",
    "        for e in edges:\n",
    "            x, y = e[0], e[1]\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        dist = [[float('inf')] * 2 for _ in range(n + 1)]\n",
    "        dist[1][0] = 0\n",
    "        q = deque([(1, 0)])\n",
    "        while dist[n][1] == float('inf'):\n",
    "            p = q.popleft()\n",
    "            for y in graph[p[0]]:\n",
    "                d = p[1] + 1\n",
    "                if d < dist[y][0]:\n",
    "                    dist[y][0] = d\n",
    "                    q.append((y, d))\n",
    "                elif dist[y][0] < d < dist[y][1]:\n",
    "                    dist[y][1] = d\n",
    "                    q.append((y, d))\n",
    "        ans = 0\n",
    "        for _ in range(dist[n][1]):\n",
    "            if ans % (change * 2) >= change:\n",
    "                ans += change * 2 - ans % (change * 2)\n",
    "            ans += time\n",
    "        return ans\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        # cnt = [[] for _ in range(n)]\n",
    "        # cnt[0]=[0]\n",
    "        # g = [[] for _ in range(n)]\n",
    "        # for u,v in edges:\n",
    "        #     g[u-1].append(v-1)\n",
    "        #     g[v-1].append(u-1)\n",
    "        # q=[(0, 0)]\n",
    "        # while len(q)>0:\n",
    "        #     x, step = q[0]\n",
    "        #     for child in g[x]:\n",
    "        #         if len(cnt[child])<2:\n",
    "        #             if step+1 not in cnt[child]:\n",
    "        #                 cnt[child].append(step+1)\n",
    "        #             cnt[child].sort()\n",
    "        #             q.append((child, step+1))\n",
    "        #     q.pop(0)\n",
    "        # step=cnt[-1][1]\n",
    "        # print(cnt, step)\n",
    "        graph = [[] for _ in range(n + 1)]\n",
    "        for e in edges:\n",
    "            x, y = e[0], e[1]\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "\n",
    "        # dist[i][0] 表示从 1 到 i 的最短路长度，dist[i][1] 表示从 1 到 i 的严格次短路长度\n",
    "        dist = [[float('inf')] * 2 for _ in range(n + 1)]\n",
    "        dist[1][0] = 0\n",
    "        q = deque([(1, 0)])\n",
    "        while dist[n][1] == float('inf'):\n",
    "            p = q.popleft()\n",
    "            for y in graph[p[0]]:\n",
    "                d = p[1] + 1\n",
    "                if d < dist[y][0]:\n",
    "                    dist[y][0] = d\n",
    "                    q.append((y, d))\n",
    "                elif dist[y][0] < d < dist[y][1]:\n",
    "                    dist[y][1] = d\n",
    "                    q.append((y, d))\n",
    "\n",
    "        step=dist[n][1]\n",
    "        res=0\n",
    "        while step>0:\n",
    "            res+=time\n",
    "            if (res//change)%2!=0 and step!=1:\n",
    "                res=(res//change+1)*change\n",
    "            step-=1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        graph = [[] for _ in range(n + 1)]\n",
    "        for e in edges:\n",
    "            x, y = e[0], e[1]\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "\n",
    "        # dist[i][0] 表示从 1 到 i 的最短路长度，dist[i][1] 表示从 1 到 i 的严格次短路长度\n",
    "        dist = [[float('inf')] * 2 for _ in range(n + 1)]\n",
    "        dist[1][0] = 0\n",
    "        q = deque([(1, 0)])\n",
    "        while dist[n][1] == float('inf'):\n",
    "            p = q.popleft()\n",
    "            for y in graph[p[0]]:\n",
    "                d = p[1] + 1\n",
    "                if d < dist[y][0]:\n",
    "                    dist[y][0] = d\n",
    "                    q.append((y, d))\n",
    "                elif dist[y][0] < d < dist[y][1]:\n",
    "                    dist[y][1] = d\n",
    "                    q.append((y, d))\n",
    "\n",
    "        ans = 0\n",
    "        for _ in range(dist[n][1]):\n",
    "            if ans % (change * 2) >= change:\n",
    "                ans += change * 2 - ans % (change * 2)\n",
    "            ans += time\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        graph = [[] for _ in range(n + 1)]\n",
    "        for e in edges:\n",
    "            x, y = e[0], e[1]\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "\n",
    "        # dist[i][0] 表示从 1 到 i 的最短路长度，dist[i][1] 表示从 1 到 i 的严格次短路长度\n",
    "        dist = [[float('inf')] * 2 for _ in range(n + 1)]\n",
    "        dist[1][0] = 0\n",
    "        q = deque([(1, 0)])\n",
    "        while q:\n",
    "            p = q.popleft()\n",
    "            for y in graph[p[0]]:\n",
    "                d = p[1] + 1\n",
    "                if d < dist[y][0]:\n",
    "                    dist[y][0] = d\n",
    "                    q.append((y, d))\n",
    "                elif dist[y][0] < d < dist[y][1]:\n",
    "                    dist[y][1] = d\n",
    "                    q.append((y, d))\n",
    "\n",
    "        ans = 0\n",
    "        for _ in range(dist[n][1]):\n",
    "            if ans % (change * 2) >= change:\n",
    "                ans += change * 2 - ans % (change * 2)\n",
    "            ans += time\n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq as hq\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        ad={i:[] for i in range(1,n+1)}\n",
    "        dis=[[float('inf')]*(n+1) for i in range(2)]\n",
    "        for s,e in edges:\n",
    "            ad[s].append(e)\n",
    "            ad[e].append(s)\n",
    "        heap=[]\n",
    "        hq.heappush(heap,[0,1])\n",
    "        mi=float(\"inf\")\n",
    "        k=0\n",
    "        while dis[1][n]==float(\"inf\"):\n",
    "            curt,curn = hq.heappop(heap)\n",
    "            x=curt//change\n",
    "            if x%2!=0:\n",
    "                curt=change*(x+1)\n",
    "            for nexn in ad[curn]:\n",
    "                net=curt+time\n",
    "                if dis[0][nexn]> net:\n",
    "                    dis[0][nexn]=net\n",
    "                    hq.heappush(heap,[net,nexn])\n",
    "                elif dis[1][nexn] > net>dis[0][nexn]:\n",
    "                    dis[1][nexn]=net\n",
    "                    hq.heappush(heap,[net,nexn])\n",
    "\n",
    "        return dis[1][n]\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        graph = [[] for _ in range(n + 1)]\n",
    "        for e in edges:\n",
    "            x, y = e[0], e[1]\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "\n",
    "        # dist[i][0] 表示从 1 到 i 的最短路长度，dist[i][1] 表示从 1 到 i 的严格次短路长度\n",
    "        dist = [[float('inf')] * 2 for _ in range(n + 1)]\n",
    "        dist[1][0] = 0\n",
    "        q = deque([(1, 0)])\n",
    "        while dist[n][1] == float('inf'):\n",
    "            p = q.popleft()\n",
    "            for y in graph[p[0]]:\n",
    "                d = p[1] + 1\n",
    "                if d < dist[y][0]:\n",
    "                    dist[y][0] = d\n",
    "                    q.append((y, d))\n",
    "                elif dist[y][0] < d < dist[y][1]:\n",
    "                    dist[y][1] = d\n",
    "                    q.append((y, d))\n",
    "\n",
    "        ans = 0\n",
    "        for _ in range(dist[n][1]):\n",
    "            if ans % (change * 2) >= change:\n",
    "                ans += change * 2 - ans % (change * 2)\n",
    "            ans += time\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        graph = [[] for _ in range(n + 1)]\n",
    "        for e in edges:\n",
    "            x, y = e[0], e[1]\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "\n",
    "        # dist[i][0] 表示从 1 到 i 的最短路长度，dist[i][1] 表示从 1 到 i 的严格次短路长度\n",
    "        dist = [[float('inf')] * 2 for _ in range(n + 1)]\n",
    "        dist[1][0] = 0\n",
    "        q = deque([(1, 0)])\n",
    "        while dist[n][1] == float('inf'):\n",
    "            p = q.popleft()\n",
    "            for y in graph[p[0]]:\n",
    "                d = p[1] + 1\n",
    "                if d < dist[y][0]:\n",
    "                    dist[y][0] = d\n",
    "                    q.append((y, d))\n",
    "                elif dist[y][0] < d < dist[y][1]:\n",
    "                    dist[y][1] = d\n",
    "                    q.append((y, d))\n",
    "\n",
    "        ans = 0\n",
    "        for _ in range(dist[n][1]):\n",
    "            if ans % (change * 2) >= change:\n",
    "                ans += change * 2 - ans % (change * 2)\n",
    "            ans += time\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        graph = [[] for _ in range(n + 1)]\n",
    "        for e in edges:\n",
    "            x, y = e[0], e[1]\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "\n",
    "        # dist[i][0] 表示从 1 到 i 的最短路长度，dist[i][1] 表示从 1 到 i 的严格次短路长度\n",
    "        dist = [[float('inf')] * 2 for _ in range(n + 1)]\n",
    "        dist[1][0] = 0\n",
    "        q = deque([(1, 0)])\n",
    "        while dist[n][1] == float('inf'):\n",
    "            p = q.popleft()\n",
    "            for y in graph[p[0]]:\n",
    "                d = p[1] + 1\n",
    "                if d < dist[y][0]:\n",
    "                    dist[y][0] = d\n",
    "                    q.append((y, d))\n",
    "                elif dist[y][0] < d < dist[y][1]:\n",
    "                    dist[y][1] = d\n",
    "                    q.append((y, d))\n",
    "\n",
    "        ans = 0\n",
    "        for _ in range(dist[n][1]):\n",
    "            if ans % (change * 2) >= change:\n",
    "                ans += change * 2 - ans % (change * 2)\n",
    "            ans += time\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        graph = [[] for _ in range(n + 1)]\n",
    "        for e in edges:\n",
    "            x, y = e[0], e[1]\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        \n",
    "        dist = [[float('inf')] * 2 for _ in range(n + 1)]\n",
    "        dist[1][0] = 0\n",
    "        q = deque([(1, 0)])\n",
    "        while dist[n][1] == float('inf'):\n",
    "            p = q.popleft()\n",
    "            for y in graph[p[0]]:\n",
    "                d = p[1] + 1\n",
    "                if d < dist[y][0]:\n",
    "                    dist[y][0] = d\n",
    "                    q.append((y, d))\n",
    "                if dist[y][0] < d < dist[y][1]:\n",
    "                    dist[y][1] = d\n",
    "                    q.append((y, d))\n",
    "        ans = 0\n",
    "        for _ in range(dist[n][1]):\n",
    "            if ans % (change * 2) >= change:\n",
    "                ans += change * 2 - ans % (change * 2)\n",
    "            ans += time\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        graph = [[] for _ in range(n + 1)]\n",
    "        for e in edges:\n",
    "            x, y = e[0], e[1]\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "\n",
    "        # dist[i][0] 表示从 1 到 i 的最短路长度，dist[i][1] 表示从 1 到 i 的严格次短路长度\n",
    "        dist = [[float('inf')] * 2 for _ in range(n + 1)]\n",
    "        dist[1][0] = 0\n",
    "        q = deque([(1, 0)])\n",
    "        while dist[n][1] == float('inf'):\n",
    "            p = q.popleft()\n",
    "            for y in graph[p[0]]:\n",
    "                d = p[1] + 1\n",
    "                if d < dist[y][0]:\n",
    "                    dist[y][0] = d\n",
    "                    q.append((y, d))\n",
    "                elif dist[y][0] < d < dist[y][1]:\n",
    "                    dist[y][1] = d\n",
    "                    q.append((y, d))\n",
    "\n",
    "        ans = 0\n",
    "        for _ in range(dist[n][1]):\n",
    "            if ans % (change * 2) >= change:\n",
    "                ans += change * 2 - ans % (change * 2)\n",
    "            ans += time\n",
    "        return ans\n",
    "\n",
    "\n",
    "# 作者：LeetCode-Solution\n",
    "# 链接：https://leetcode-cn.com/problems/second-minimum-time-to-reach-destination/solution/dao-da-mu-de-di-de-di-er-duan-shi-jian-b-05i0/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        find=0\n",
    "        cur=-1\n",
    "        e=collections.defaultdict(list)\n",
    "        for i,j in edges:\n",
    "            e[i].append(j)\n",
    "            e[j].append(i)\n",
    "        dist = [[float('inf')] * 2 for _ in range(n + 1)]\n",
    "        dist[1][0] = 0\n",
    "        q = deque([(1, 0)])\n",
    "        while dist[n][1] == float('inf'):\n",
    "            p = q.popleft()\n",
    "            for y in e[p[0]]:\n",
    "                d = p[1] + 1\n",
    "                if d < dist[y][0]:\n",
    "                    dist[y][0] = d\n",
    "                    q.append((y, d))\n",
    "                elif dist[y][0] < d < dist[y][1]:\n",
    "                    dist[y][1] = d\n",
    "                    q.append((y, d))\n",
    "        t= dist[n][1]\n",
    "        tt=0\n",
    "        ans=0\n",
    "        for k in range(t):\n",
    "            tt+=time\n",
    "            ans+=time \n",
    "            if k==t-1:\n",
    "                break\n",
    "            #print(tt,ans)\n",
    "            while tt>=change*2:\n",
    "                tt=tt-change*2\n",
    "            if tt>=change:\n",
    "                ans=ans+change*2-tt \n",
    "                tt=0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        arr=[[] for i in range(n+1)]\n",
    "        dist1=[float('inf') for i in range(n+1)]\n",
    "        dist2=[float('inf') for i in range(n+1)]\n",
    "        dist1[1]=0\n",
    "        for edge in edges:\n",
    "            arr[edge[0]].append(edge[1])\n",
    "            arr[edge[1]].append(edge[0])\n",
    "        pq=PriorityQueue()\n",
    "        pq.put((0,1))\n",
    "        while not pq.empty():\n",
    "            dis,node=pq.get()\n",
    "            if dis>dist2[node]:\n",
    "                continue\n",
    "            for new_node in arr[node]:\n",
    "                if dis+1<dist1[new_node]:\n",
    "                    dist2[new_node]=dist1[new_node]\n",
    "                    dist1[new_node]=dis+1\n",
    "                    pq.put((dist1[new_node], new_node))\n",
    "                elif dist1[new_node]!=dis+1 and dis+1<dist2[new_node]:\n",
    "                    dist2[new_node]=dis+1\n",
    "                    pq.put((dist2[new_node], new_node))\n",
    "        ans=dist2[n]*time\n",
    "        vis,tmp=0,0\n",
    "        for i in range(1,dist2[n]+1):\n",
    "            ans+=tmp\n",
    "            vis+=time\n",
    "            ds=vis%(2*change)\n",
    "            if ds>=change:\n",
    "                ds-=change\n",
    "                tmp=change-ds\n",
    "                vis+=tmp\n",
    "            else:\n",
    "                tmp=0\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "import math\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        dist1 = [math.inf] * (n + 1)\n",
    "        dist2 = [math.inf] * (n + 1)\n",
    "        dist1[1] = 0\n",
    "        h = [[0, 1]]\n",
    "        while h:\n",
    "            d, x = heapq.heappop(h)\n",
    "            t = d % (2 * change)\n",
    "            if t >= change:\n",
    "                d += 2 * change - t\n",
    "            for y in g[x]:\n",
    "                if d + time < dist1[y]:\n",
    "                    dist2[y] = dist1[y]\n",
    "                    dist1[y] = d + time\n",
    "                    heapq.heappush(h, [d + time, y])\n",
    "                elif dist1[y] < d + time < dist2[y]:\n",
    "                    dist2[y] = d + time\n",
    "                    heapq.heappush(h, [d + time, y])\n",
    "        # print(dist1)\n",
    "        # print(dist2)\n",
    "        return dist2[n]\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for [a,b] in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        dist = [[float('inf')] * 2 for _ in range(n+1)]\n",
    "        vis = [0] * (n+1)\n",
    "        dist[1][0] = 0\n",
    "        Q = deque([(dist[1][0], 1)])\n",
    "        while Q:\n",
    "            d, u = Q.popleft() \n",
    "            if vis[u] >= 2:\n",
    "                continue \n",
    "            vis[u] += 1\n",
    "            for v in g[u]:\n",
    "                if dist[v][0] > d + 1:\n",
    "                    dist[v][1] = dist[v][0]\n",
    "                    dist[v][0] = d + 1\n",
    "                    Q.append((dist[v][0], v))\n",
    "                elif dist[v][0] < d + 1 and dist[v][1] > d + 1:\n",
    "                    dist[v][1] = d + 1\n",
    "                    Q.append((dist[v][1], v))\n",
    "        ans = 0\n",
    "        for i in range(1, int(dist[n][1])):\n",
    "            ans += time \n",
    "            if ans % (2 * change) >= change:\n",
    "                ans += change- ans % change \n",
    "        ans += time \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        e = collections.defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            e[u].append(v)\n",
    "            e[v].append(u)\n",
    "        dist1 = [float('inf')] * (n + 1)\n",
    "        dist1[1] = 0\n",
    "        dist2 = [float('inf')] * (n + 1)\n",
    "        minheap = [(0, 1)]\n",
    "        while minheap:\n",
    "            cost, n1 = heapq.heappop(minheap)\n",
    "            for n2 in e[n1]:\n",
    "                a, b = divmod(cost, change)\n",
    "                wait = 0 if a % 2 == 0 else change - b\n",
    "                newcost = cost + time + wait\n",
    "                if newcost < dist1[n2]:\n",
    "                    dist2[n2] = dist1[n2]\n",
    "                    dist1[n2] = newcost\n",
    "                    heapq.heappush(minheap, (newcost, n2))\n",
    "                elif dist1[n2] < newcost < dist2[n2]:\n",
    "                    dist2[n2] = newcost\n",
    "                    heapq.heappush(minheap, (newcost, n2)) \n",
    "        return dist2[n]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        e = collections.defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            e[u].append(v)\n",
    "            e[v].append(u)\n",
    "        dist1 = [float('inf')] * (n + 1)\n",
    "        dist1[1] = 0\n",
    "        dist2 = [float('inf')] * (n + 1)\n",
    "        minheap = [(0, 1)]\n",
    "        while minheap:\n",
    "            cost, n1 = heapq.heappop(minheap)\n",
    "            for n2 in e[n1]:\n",
    "                a, b = divmod(cost, change)\n",
    "                wait = 0 if a % 2 == 0 else change - b\n",
    "                newcost = cost + time + wait\n",
    "                if newcost < dist1[n2]:\n",
    "                    dist2[n2] = dist1[n2]\n",
    "                    dist1[n2] = newcost\n",
    "                    heapq.heappush(minheap, (newcost, n2))\n",
    "                elif dist1[n2] < newcost < dist2[n2]:\n",
    "                    dist2[n2] = newcost\n",
    "                    heapq.heappush(minheap, (newcost, n2)) \n",
    "        return dist2[n]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        firsttime = [float(\"-inf\")] * (n+1) #用firsttime记录第一次、第二次遍历到的时间\n",
    "        visited = set() #记录已经第二次遍历过的点\n",
    "        v = defaultdict(list)\n",
    "        firsttime[1] = 0\n",
    "        for i, j in edges:\n",
    "            v[i].append(j)\n",
    "            v[j].append(i)\n",
    "        #BFS\n",
    "        q = deque([(1,0)])\n",
    "        while q:\n",
    "            node, dis = q.popleft()\n",
    "            for nxt in v[node]:\n",
    "                if nxt not in visited:\n",
    "                    if firsttime[nxt] == float(\"-inf\"):#如果是第一次遍历到nxt\n",
    "                        firsttime[nxt] = dis + 1\n",
    "                    elif dis + 1 > firsttime[nxt]:#如果是第二次遍历到nxt\n",
    "                        firsttime[nxt] = dis + 1\n",
    "                        visited.add(nxt)\n",
    "                    else:\n",
    "                        continue\n",
    "                    q.append((nxt, dis+1))\n",
    "            \n",
    "        k = firsttime[n]\n",
    "        minute = 0\n",
    "        while k:\n",
    "            minute += time\n",
    "            k -= 1\n",
    "            if k == 0:\n",
    "                break\n",
    "            if minute < change:\n",
    "                continue\n",
    "            lightred = minute // change\n",
    "            if lightred % 2:\n",
    "                minute = (lightred + 1) * change\n",
    "        return minute"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        dist1 = [inf] * (n + 1)\n",
    "        dist2 = [inf] * (n + 1)\n",
    "        dist1[1] = 0\n",
    "        q = []\n",
    "        heappush(q, (0, 1))\n",
    "        while q:\n",
    "            d, u = heappop(q)\n",
    "            # if d > dist[x]:\n",
    "            #     continue\n",
    "            for y in g[u]:\n",
    "                nd = d + time\n",
    "                a, b = d // change, d % change\n",
    "                if a % 2:\n",
    "                    nd += change - b\n",
    "                if dist1[y] > nd:\n",
    "                    dist2[y] = dist1[y]\n",
    "                    dist1[y] = nd\n",
    "                    heappush(q, (dist1[y], y))\n",
    "                    # 次短路可能是最短路走到离当前最近的节点，再走回来，需要确保每次最短路或者次短路被更新的时候，都进行入堆操作\n",
    "                    heappush(q, (dist2[y], y))\n",
    "                elif dist2[y] > nd > dist1[y]:\n",
    "                    dist2[y] = nd\n",
    "                    heappush(q, (dist2[y], y))\n",
    "        return dist2[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for [a,b] in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        dist1 = [float('inf')] * (n+1) \n",
    "        dist2 = [float('inf')] * (n+1)\n",
    "        vis = [0] * (n+1)\n",
    "        \n",
    "        dist1[1] = 0\n",
    "        Q = [(0,1)]\n",
    "        while Q:\n",
    "            d, u = heapq.heappop(Q)\n",
    "            if d > dist2[u]:\n",
    "                continue \n",
    "            vis[u] += 1\n",
    "            nd = d \n",
    "            if d % (2 * change) >= change:\n",
    "                nd = d + 2 * change - d % (2 * change) \n",
    "            \n",
    "            for v in g[u]:\n",
    "                if dist1[v] > nd + time:\n",
    "                    dist2[v] = dist1[v]\n",
    "                    dist1[v] = nd + time\n",
    "                    heapq.heappush(Q,(dist1[v], v))\n",
    "                    #Q.append((dist1[v], v)) \n",
    "                elif dist1[v] < nd + time and  dist2[v] > nd + time:\n",
    "                    dist2[v] = nd + time\n",
    "                    heapq.heappush(Q,(dist2[v], v))\n",
    "                    #Q.append((dist2[v], v)) \n",
    "\n",
    "        return dist2[n]\n",
    "        ans = 0 \n",
    "        for i in range(1, dist2[n]):\n",
    "            ans += time \n",
    "            if ans % (2 * change) >= change:\n",
    "                ans += change - ans%change \n",
    "        ans += time \n",
    "\n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        # 1. O(V+E) build adjacency list of undirected graph\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "\n",
    "        # 2. O((V+E)logV) run heap-optimized Dijkstra's algorithm\n",
    "        dist = self.bfs(0, g)\n",
    "\n",
    "        ans = 0 \n",
    "        for i in range(dist[n-1]):\n",
    "            q, r = divmod(ans, change)\n",
    "            if q % 2:   # red\n",
    "                wait = change - r \n",
    "            else:       # green\n",
    "                wait = 0\n",
    "            ans += time + wait \n",
    "\n",
    "        return ans \n",
    "    \n",
    "\n",
    "    def bfs(self, start: int, g: List[List[int]]) -> List[int]:\n",
    "        n = len(g)\n",
    "        dist1 = [math.inf] * n     # shortest path\n",
    "        dist2 = [math.inf] * n     # second shortest path\n",
    "        dist1[start] = 0 \n",
    "        \n",
    "        queue = deque([(0, start)]) \n",
    "        while queue:\n",
    "            d, u = queue.popleft()\n",
    "            d += 1\n",
    "            for v in g[u]:\n",
    "                if dist1[v] > d:\n",
    "                    dist1[v] = d\n",
    "                    queue.append((d, v))\n",
    "\n",
    "                elif dist1[v] < d < dist2[v]:\n",
    "                    dist2[v] = d \n",
    "                    queue.append((d, v))\n",
    "        return dist2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        \n",
    "        graph = [[] for _ in range(n+1)]\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        \n",
    "        # (到达时间，节点)\n",
    "        pq = [(0, 1)]\n",
    "        # 到达每个节点的最短和第二短时间\n",
    "        dist = [[float('inf'), float('inf')] for _ in range(n+1)]\n",
    "        dist[1][0] = 0\n",
    "\n",
    "        while pq:\n",
    "            curr_time, node = heapq.heappop(pq)\n",
    "            if node == n:\n",
    "                if curr_time > dist[n][0]:\n",
    "                    return curr_time\n",
    "            # 检查信号灯颜色\n",
    "            if (curr_time // change) % 2 == 1:\n",
    "                curr_time += change - curr_time % change\n",
    "            for nei in graph[node]:\n",
    "                d = curr_time + time\n",
    "                if d < dist[nei][0]:\n",
    "                    dist[nei][0], dist[nei][1] = d, dist[nei][0]\n",
    "                    heapq.heappush(pq, (d, nei))\n",
    "                elif dist[nei][0] < d < dist[nei][1]:\n",
    "                    dist[nei][1] = d\n",
    "                    heapq.heappush(pq, (d, nei))\n",
    "                    \n",
    "        return dist[n][1]\n",
    "\n",
    "    # # 例子\n",
    "    # n = 4\n",
    "    # edges = [[1,2],[2,3],[3,4]]\n",
    "    # time = 10\n",
    "    # change = 5\n",
    "    # print(networkDelayTime(n, edges, time, change))  # 输出应该是第二短的时间\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "        \n",
    "        dis = [[inf, inf] for _ in range(n)]\n",
    "        dis[0][0] = 0\n",
    "        q = deque([(0, 0)])\n",
    "        while dis[n-1][1] == inf:\n",
    "            d, x = q.popleft()\n",
    "            for y in g[x]:\n",
    "                if d + 1 < dis[y][0]:\n",
    "                    dis[y][0] = d + 1\n",
    "                    q.append((d + 1, y))\n",
    "                elif dis[y][0] < d + 1 < dis[y][1]:\n",
    "                    dis[y][1] = d + 1\n",
    "                    q.append((d + 1, y))\n",
    "        \n",
    "        ans = 0\n",
    "        for _ in range(dis[n-1][1]):\n",
    "            if ans % (change * 2) >= change:\n",
    "                ans += change * 2 - ans % (change * 2)\n",
    "            ans += time\n",
    "\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "        \n",
    "        dis = [[inf, inf] for _ in range(n)]\n",
    "        dis[0][0] = 0\n",
    "        q = [(0, 0)]\n",
    "        while dis[n-1][1] == inf:\n",
    "            d, x = heappop(q)\n",
    "            for y in g[x]:\n",
    "                if d + 1 < dis[y][0]:\n",
    "                    dis[y][0] = d + 1\n",
    "                    heappush(q, (d + 1, y))\n",
    "                elif dis[y][0] < d + 1 < dis[y][1]:\n",
    "                    dis[y][1] = d + 1\n",
    "                    heappush(q, (d + 1, y))\n",
    "        \n",
    "        ans = 0\n",
    "        for _ in range(dis[n-1][1]):\n",
    "            if ans % (change * 2) >= change:\n",
    "                ans += change * 2 - ans % (change * 2)\n",
    "            ans += time\n",
    "\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            graph[u-1].append(v-1)\n",
    "            graph[v-1].append(u-1)\n",
    "\n",
    "        heap = [(0, 0)]\n",
    "        dist1, dist2 = [math.inf] * n, [math.inf] * n\n",
    "        dist1[0] = 0\n",
    "        while heap:\n",
    "            d, cur = heapq.heappop(heap)\n",
    "            if d > dist2[cur]:\n",
    "                continue\n",
    "            for nxt in graph[cur]:\n",
    "                if d + 1 < dist1[nxt]:\n",
    "                    dist2[nxt], dist1[nxt] = dist1[nxt], d + 1\n",
    "                    heapq.heappush(heap, (d+1, nxt))\n",
    "                elif dist1[nxt] < d + 1 < dist2[nxt]:\n",
    "                    dist2[nxt] = d + 1\n",
    "                    heapq.heappush(heap, (d+1, nxt))\n",
    "\n",
    "        min_dist = dist2[-1]\n",
    "        ans = 0\n",
    "        while min_dist > 0:\n",
    "            ans += time\n",
    "            min_dist -= 1\n",
    "            if (ans // change) & 1 and min_dist > 0:\n",
    "                ans = (ans // change + 1) * change\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            graph[x-1].append(y-1)\n",
    "            graph[y-1].append(x-1)\n",
    "        # dist[i][0] 表示从 0 到 i 的最短路长度，dist[i][1] 表示从 0 到 i 的严格次短路长度\n",
    "        dist = [[math.inf] * 2 for _ in range(n)]\n",
    "        dist[0][0] = 0\n",
    "        q = collections.deque()\n",
    "        q.append((0,0))\n",
    "        while q:\n",
    "            w,x = q.popleft()\n",
    "            #不能剪枝\n",
    "            for y in graph[x]:\n",
    "                d = w + 1\n",
    "                if d < dist[y][0]:\n",
    "                    dist[y][0] = d\n",
    "                    q.append((d,y))\n",
    "                elif dist[y][0] < d < dist[y][1]:\n",
    "                    dist[y][1] = d\n",
    "                    q.append((d,y))\n",
    "        ans = time\n",
    "        # print(dist)\n",
    "        for _ in range(dist[n-1][1]-1):\n",
    "            if ans % (change * 2) >= change:#落在红灯区域\n",
    "                ans += change * 2 - ans % (change * 2)#减去前面已经过去的绿灯\n",
    "            ans += time\n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            graph[x-1].append(y-1)\n",
    "            graph[y-1].append(x-1)\n",
    "        # dist[i][0] 表示从 0 到 i 的最短路长度，dist[i][1] 表示从 0 到 i 的严格次短路长度\n",
    "        dist = [[math.inf] * 2 for _ in range(n)]\n",
    "        dist[0][0] = 0\n",
    "        q = collections.deque()\n",
    "        q.append((0,0))\n",
    "        while q:\n",
    "            w,x = q.popleft()\n",
    "            #不能剪枝\n",
    "            for y in graph[x]:\n",
    "                d = w + 1\n",
    "                if d < dist[y][0]:\n",
    "                    dist[y][0] = d\n",
    "                    q.append((d,y))\n",
    "                elif dist[y][0] < d < dist[y][1]:\n",
    "                    dist[y][1] = d\n",
    "                    q.append((d,y))\n",
    "        ans = 0\n",
    "        # print(dist)\n",
    "        for _ in range(dist[n-1][1]):\n",
    "            if ans % (change * 2) >= change:\n",
    "                ans += change * 2 - ans % (change * 2)\n",
    "            ans += time\n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)\n",
    "        dist1 = [inf] * n\n",
    "        dist2 = [inf] * n\n",
    "        dist1[0] = 0\n",
    "        h = [(0, 0)]\n",
    "        while h:\n",
    "            d, u = heapq.heappop(h)\n",
    "            if d != dist1[u] and d != dist2[u]:\n",
    "                continue\n",
    "            for v in g[u]:\n",
    "                a, b = d // change, d % change\n",
    "                wait = 0 if a % 2 == 0 else change - b\n",
    "                t = d + wait + time\n",
    "                if t < dist1[v]:\n",
    "                    dist2[v] = dist1[v]\n",
    "                    dist1[v] = t\n",
    "                    heapq.heappush(h, (t, v))\n",
    "                elif dist1[v] < t and t < dist2[v]:\n",
    "                    dist2[v] = t\n",
    "                    heapq.heappush(h, (t, v))\n",
    "        return dist2[-1]                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)\n",
    "        dist1 = [inf] * n\n",
    "        dist2 = [inf] * n\n",
    "        dist1[0] = 0\n",
    "        h = [(0, 0)]\n",
    "        while h:\n",
    "            d, u = heapq.heappop(h)\n",
    "            if d != dist1[u] and d != dist2[u]:\n",
    "                continue\n",
    "            for v in g[u]:\n",
    "                a, b = d // change, d % change\n",
    "                wait = 0 if a % 2 == 0 else change - b\n",
    "                t = d + wait + time\n",
    "                if t < dist1[v]:\n",
    "                    dist2[v] = dist1[v]\n",
    "                    dist1[v] = t\n",
    "                    heapq.heappush(h, (t, v))\n",
    "                elif dist1[v] < t and t < dist2[v]:\n",
    "                    dist2[v] = t\n",
    "                    heapq.heappush(h, (t, v))\n",
    "        return dist2[-1]                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            graph[u-1].append(v-1)\n",
    "            graph[v-1].append(u-1)\n",
    "\n",
    "        heap = [(0, 0)]\n",
    "        dist1, dist2 = [math.inf] * n, [math.inf] * n\n",
    "        dist1[0] = 0\n",
    "        while heap:\n",
    "            d, cur = heapq.heappop(heap)\n",
    "            if d > dist2[cur]:\n",
    "                continue\n",
    "\n",
    "            if d % (change * 2) >= change:\n",
    "                d = (d // (change * 2) + 1) * (change * 2)\n",
    "            d += time\n",
    "            for nxt in graph[cur]:\n",
    "                if d < dist1[nxt]:\n",
    "                    dist1[nxt], dist2[nxt] = d, dist1[nxt]\n",
    "                    heapq.heappush(heap, (d, nxt))\n",
    "                elif dist1[nxt] < d < dist2[nxt]:\n",
    "                    dist2[nxt] = d\n",
    "                    heapq.heappush(heap, (d, nxt))\n",
    "\n",
    "        return dist2[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        cnt = [[] for _ in range(n)]\n",
    "        cnt[0]=[0]\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u,v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "        q=deque([(0, 0)])\n",
    "        while len(cnt[-1])<2:\n",
    "            x, step = q.popleft()\n",
    "            for child in g[x]:\n",
    "                if len(cnt[child])<2:\n",
    "                    if step+1 not in cnt[child]:\n",
    "                        cnt[child].append(step+1)\n",
    "                    cnt[child].sort()\n",
    "                    q.append((child, step+1))\n",
    "        step=cnt[-1][1]\n",
    "        # print(cnt, step)\n",
    "        res=0\n",
    "        while step>0:\n",
    "            res+=time\n",
    "            if (res//change)%2!=0 and step!=1:\n",
    "                res=(res//change+1)*change\n",
    "            step-=1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        cnt = [[] for _ in range(n)]\n",
    "        cnt[0]=[0]\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u,v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "        q=deque([(0, 0)])\n",
    "        while len(cnt[-1])<2:\n",
    "            x, step = q.popleft()\n",
    "            for child in g[x]:\n",
    "                if len(cnt[child])<2:\n",
    "                    if step+1 not in cnt[child]:\n",
    "                        cnt[child].append(step+1)\n",
    "                    cnt[child].sort()\n",
    "                    q.append((child, step+1))\n",
    "        step=cnt[-1][1]\n",
    "        # print(cnt, step)\n",
    "        res=0\n",
    "        while step>0:\n",
    "            res+=time\n",
    "            if (res//change)%2!=0 and step!=1:\n",
    "                res=(res//change+1)*change\n",
    "            step-=1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        cnt = [[] for _ in range(n)]\n",
    "        cnt[0]=[0]\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u,v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "        q=[(0, 0)]\n",
    "        while len(q)>0:\n",
    "            x, step = q[0]\n",
    "            for child in g[x]:\n",
    "                if len(cnt[child])<2:\n",
    "                    if step+1 not in cnt[child]:\n",
    "                        cnt[child].append(step+1)\n",
    "                    cnt[child].sort()\n",
    "                    q.append((child, step+1))\n",
    "            q.pop(0)\n",
    "        step=cnt[-1][1]\n",
    "        # print(cnt, step)\n",
    "        res=0\n",
    "        while step>0:\n",
    "            res+=time\n",
    "            if (res//change)%2!=0 and step!=1:\n",
    "                res=(res//change+1)*change\n",
    "            step-=1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        # 返回从节点 1 到节点 n 需要的 第二短时间 \n",
    "        dist = [[float('inf')] * 2 for _ in range(n)]\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x-1].append(y-1)\n",
    "            g[y-1].append(x-1)\n",
    "        dist[0][0] = 0\n",
    "        queue = collections.deque()\n",
    "        queue.append((0,0)) #startnode = 0,w = 0\n",
    "\n",
    "        while queue:\n",
    "            x,w = queue.popleft()\n",
    "            # if w > dist[x][1]:#大于第二最短路径\n",
    "            #     continue\n",
    "            for y in g[x]:\n",
    "                tmpw = w + 1\n",
    "                # if tmpw >= dist[y][1]:#大于第二最短路径\n",
    "                #     continue\n",
    "                if tmpw < dist[y][0]:#小于第一最短路径\n",
    "                    dist[y][1] = dist[y][0]\n",
    "                    dist[y][0] = tmpw\n",
    "                    queue.append((y,tmpw))\n",
    "                elif dist[y][0] < tmpw < dist[y][1]:#介于第一第二路径间\n",
    "                    dist[y][1] = tmpw\n",
    "                    queue.append((y,tmpw))\n",
    "        ans = 0\n",
    "        lujin = dist[-1][-1]\n",
    "        for _ in range(lujin):\n",
    "            if ans%(change*2)>=change:\n",
    "                #落地红灯区域，加上等待红灯的时间\n",
    "                ans +=2*change - ans%(change*2)\n",
    "            ans += time #加上本就需要的时间\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        # 返回从节点 1 到节点 n 需要的 第二短时间 \n",
    "        dist = [[float('inf')] * 2 for _ in range(n)]\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x-1].append(y-1)\n",
    "            g[y-1].append(x-1)\n",
    "        dist[0][0] = 0\n",
    "        hq = [(0,0)]\n",
    "        # queue.put((0,0)) #startnode = 0,w = 0\n",
    "\n",
    "        while hq:\n",
    "            w,x = heapq.heappop(hq)\n",
    "            if w > dist[x][1]:#大于第二最短路径\n",
    "                continue\n",
    "            for y in g[x]:\n",
    "                tmpw = w + 1\n",
    "                # if tmpw >= dist[y][1]:#大于第二最短路径\n",
    "                #     continue\n",
    "                if tmpw < dist[y][0]:#小于第一最短路径\n",
    "                    # dist[y][1] = dist[y][0]\n",
    "                    dist[y][0] = tmpw\n",
    "                    heapq.heappush(hq, (tmpw,y))\n",
    "                   \n",
    "                elif dist[y][0] < tmpw < dist[y][1]:#介于第一第二路径间\n",
    "                    dist[y][1] = tmpw\n",
    "                    heapq.heappush(hq, (tmpw,y))\n",
    "        ans = 0\n",
    "        lujin = dist[-1][-1]\n",
    "        for _ in range(lujin):\n",
    "            if ans%(change*2)>=change:\n",
    "                #落地红灯区域，加上等待红灯的时间\n",
    "                ans +=2*change - ans%(change*2)\n",
    "            ans += time #加上本就需要的时间\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        cnt = [[] for _ in range(n)]\n",
    "        cnt[0]=[0]\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u,v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "        q=deque([(0, 0)])\n",
    "        while len(cnt[-1])<2:\n",
    "            x, step = q.popleft()\n",
    "            for child in g[x]:\n",
    "                if len(cnt[child])<2:\n",
    "                    if step+1 not in cnt[child]:\n",
    "                        if len(cnt[child])==0:\n",
    "                            cnt[child].append(step+1)\n",
    "                        else:\n",
    "                            if cnt[child][0]>step+1:\n",
    "                                cnt[child] = [step+1, cnt[child][0]]\n",
    "                            else:\n",
    "                                cnt[child].append(step+1)                                \n",
    "                    q.append((child, step+1))\n",
    "        step=cnt[-1][1]\n",
    "        # print(cnt, step)\n",
    "        res=0\n",
    "        while step>0:\n",
    "            res+=time\n",
    "            if (res//change)%2!=0 and step!=1:\n",
    "                res=(res//change+1)*change\n",
    "            step-=1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        # 返回从节点 1 到节点 n 需要的 第二短时间 \n",
    "        dist = [[float('inf')] * 2 for _ in range(n)]\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x-1].append(y-1)\n",
    "            g[y-1].append(x-1)\n",
    "        dist[0][0] = 0\n",
    "        hq = [(0,0)]\n",
    "        # queue.put((0,0)) #startnode = 0,w = 0\n",
    "\n",
    "        while hq:\n",
    "            x,w = heapq.heappop(hq)\n",
    "            if w > dist[x][1]:#大于第二最短路径\n",
    "                continue\n",
    "            for y in g[x]:\n",
    "                tmpw = w + 1\n",
    "                # if tmpw >= dist[y][1]:#大于第二最短路径\n",
    "                #     continue\n",
    "                if tmpw < dist[y][0]:#小于第一最短路径\n",
    "                    dist[y][1] = dist[y][0]\n",
    "                    dist[y][0] = tmpw\n",
    "                    heapq.heappush(hq, (y,tmpw))\n",
    "                   \n",
    "                elif dist[y][0] < tmpw < dist[y][1]:#介于第一第二路径间\n",
    "                    dist[y][1] = tmpw\n",
    "                    heapq.heappush(hq, (y,tmpw))\n",
    "        ans = 0\n",
    "        lujin = dist[-1][-1]\n",
    "        for _ in range(lujin):\n",
    "            if ans%(change*2)>=change:\n",
    "                #落地红灯区域，加上等待红灯的时间\n",
    "                ans +=2*change - ans%(change*2)\n",
    "            ans += time #加上本就需要的时间\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        cnt = [[] for _ in range(n)]\n",
    "        cnt[0]=[0]\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u,v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "        q=deque([(0, 0)])\n",
    "        while len(q)>0:\n",
    "            x, step = q.popleft()\n",
    "            for child in g[x]:\n",
    "                if step+1 not in cnt[child] and len(cnt[child])<2:\n",
    "                    cnt[child].append(step+1)\n",
    "                    cnt[child].sort()\n",
    "                    q.append((child, step+1))\n",
    "        step=cnt[-1][1]\n",
    "        # print(cnt, step)\n",
    "        res=0\n",
    "        while step>0:\n",
    "            res+=time\n",
    "            if (res//change)%2!=0 and step!=1:\n",
    "                res=(res//change+1)*change\n",
    "            step-=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        cnt = [[] for _ in range(n)]\n",
    "        cnt[0]=[0]\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u,v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "        q=[(0, 0)]\n",
    "        while len(cnt[-1])<2:\n",
    "            x, step = q[0]\n",
    "            for child in g[x]:\n",
    "                if len(cnt[child])<2:\n",
    "                    if step+1 not in cnt[child]:\n",
    "                        cnt[child].append(step+1)\n",
    "                    cnt[child].sort()\n",
    "                    q.append((child, step+1))\n",
    "            q.pop(0)\n",
    "        step=cnt[-1][1]\n",
    "        # print(cnt, step)\n",
    "        res=0\n",
    "        while step>0:\n",
    "            res+=time\n",
    "            if (res//change)%2!=0 and step!=1:\n",
    "                res=(res//change+1)*change\n",
    "            step-=1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        # 返回从节点 1 到节点 n 需要的 第二短时间 \n",
    "        dist = [[float('inf')] * 2 for _ in range(n)]\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x-1].append(y-1)\n",
    "            g[y-1].append(x-1)\n",
    "        dist[0][0] = 0\n",
    "        hq = [(0,0)]\n",
    "        # queue.put((0,0)) #startnode = 0,w = 0\n",
    "\n",
    "        while hq:\n",
    "            w,x = heapq.heappop(hq)\n",
    "            if w > dist[x][1]:#大于第二最短路径\n",
    "                continue\n",
    "            for y in g[x]:\n",
    "                tmpw = w + 1\n",
    "                # if tmpw >= dist[y][1]:#大于第二最短路径\n",
    "                #     continue\n",
    "                if tmpw < dist[y][0]:#小于第一最短路径\n",
    "                    dist[y][1] = dist[y][0]\n",
    "                    dist[y][0] = tmpw\n",
    "                    heapq.heappush(hq, (tmpw,y))\n",
    "                   \n",
    "                elif dist[y][0] < tmpw < dist[y][1]:#介于第一第二路径间\n",
    "                    dist[y][1] = tmpw\n",
    "                    heapq.heappush(hq, (tmpw,y))\n",
    "        ans = 0\n",
    "        lujin = dist[-1][-1]\n",
    "        for _ in range(lujin):\n",
    "            if ans%(change*2)>=change:\n",
    "                #落地红灯区域，加上等待红灯的时间\n",
    "                ans +=2*change - ans%(change*2)\n",
    "            ans += time #加上本就需要的时间\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heapify, heappop, heappush\r\n",
    "maxTime = 100000000\r\n",
    "dist = [[0] * 2 for _ in range(10000)]\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\r\n",
    "        for i in range(n):\r\n",
    "            dist[i][0] = dist[i][1] = maxTime\r\n",
    "        conn: dict[int, list[int]] = {i: list() for i in range(n)}\r\n",
    "        for u, v in edges:\r\n",
    "            conn[u - 1].append(v - 1)\r\n",
    "            conn[v - 1].append(u - 1)\r\n",
    "        dist[0][0] = 0\r\n",
    "        dij: list[tuple[int, int]] = list()\r\n",
    "        heapify(dij)\r\n",
    "        heappush(dij, (0, 0))\r\n",
    "\r\n",
    "        while dij[0][0] < dist[n - 1][1]:\r\n",
    "            t, node = heappop(dij)\r\n",
    "            traffic = t // change\r\n",
    "            nxt_t = time + (((traffic + 1) * change) if traffic % 2 else t)\r\n",
    "            for nxt in conn[node]:\r\n",
    "                if nxt_t < dist[nxt][0]:\r\n",
    "                    dist[nxt][1] = dist[nxt][0]\r\n",
    "                    dist[nxt][0] = nxt_t\r\n",
    "                    heappush(dij, (nxt_t, nxt))\r\n",
    "                elif nxt_t != dist[nxt][0] and nxt_t < dist[nxt][1]:\r\n",
    "                    dist[nxt][1] = nxt_t\r\n",
    "                    heappush(dij, (nxt_t, nxt))\r\n",
    "        \r\n",
    "        return dist[n - 1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        # 返回从节点 1 到节点 n 需要的 第二短时间 \n",
    "        dist = [[float('inf')] * 2 for _ in range(n)]\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x-1].append(y-1)\n",
    "            g[y-1].append(x-1)\n",
    "        dist[0][0] = 0\n",
    "        hq = [(0,0)]\n",
    "        # queue.put((0,0)) #startnode = 0,w = 0\n",
    "\n",
    "        while hq:\n",
    "            x,w = heapq.heappop(hq)\n",
    "            # if w > dist[x][1]:#大于第二最短路径\n",
    "            #     continue\n",
    "            for y in g[x]:\n",
    "                tmpw = w + 1\n",
    "                # if tmpw >= dist[y][1]:#大于第二最短路径\n",
    "                #     continue\n",
    "                if tmpw < dist[y][0]:#小于第一最短路径\n",
    "                    dist[y][1] = dist[y][0]\n",
    "                    dist[y][0] = tmpw\n",
    "                    heapq.heappush(hq, (y,tmpw))\n",
    "                   \n",
    "                elif dist[y][0] < tmpw < dist[y][1]:#介于第一第二路径间\n",
    "                    dist[y][1] = tmpw\n",
    "                    heapq.heappush(hq, (y,tmpw))\n",
    "        ans = 0\n",
    "        lujin = dist[-1][-1]\n",
    "        for _ in range(lujin):\n",
    "            if ans%(change*2)>=change:\n",
    "                #落地红灯区域，加上等待红灯的时间\n",
    "                ans +=2*change - ans%(change*2)\n",
    "            ans += time #加上本就需要的时间\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        children = [[]for _ in range(n)]\n",
    "        for e in edges:\n",
    "            children[e[0]-1].append(e[1]-1)\n",
    "            children[e[1]-1].append(e[0]-1)\n",
    "        visited1 = {}\n",
    "        visited2 = {}\n",
    "        minDistHeap = [(0,0)]\n",
    "        curMin = inf\n",
    "        while minDistHeap:\n",
    "            curT, curN = heapq.heappop(minDistHeap)\n",
    "            # print(curN, curT)\n",
    "            if curN == n-1:\n",
    "                if curMin == inf:\n",
    "                    curMin = curT\n",
    "                else:\n",
    "                    if curT > curMin: return curT\n",
    "            changedTime = curT//change\n",
    "            # print(changedTime)\n",
    "            if changedTime%2 == 1:#changed odd time, is red\n",
    "                curT = (changedTime+1)*change\n",
    "            for child in children[curN]:\n",
    "                newItem = (curT+time, child)\n",
    "                if child == n-1 or child not in visited2.keys():\n",
    "                    if child not in visited1.keys():\n",
    "                        visited1[child] = newItem[0]\n",
    "                    else:\n",
    "                        if newItem[0] > visited1[child]:\n",
    "                            visited2[child] = newItem[0]\n",
    "                    heapq.heappush(minDistHeap, newItem)\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        g = defaultdict(set)\n",
    "        for a, b in edges:\n",
    "            g[a].add(b)\n",
    "            g[b].add(a)\n",
    "        \n",
    "        visited = defaultdict(int)\n",
    "        q = deque([1])\n",
    "        visited[1] = 1\n",
    "        cnt = 0\n",
    "        while q:\n",
    "            # print(cnt, q)\n",
    "            # print(visited.items())\n",
    "            # print()\n",
    "            tem_s = set()\n",
    "            size = len(q)\n",
    "            for i in range(size):\n",
    "                p = q.popleft()\n",
    "                # print(f'({p}:{visited[p]},{cnt})', end=', ')\n",
    "                # 第二次到达终点\n",
    "                if p == n and visited[n] == 2:\n",
    "                    return cnt\n",
    "                for pp in g[p]:\n",
    "                    # print(f'({pp})', end='')\n",
    "                    if visited[pp] < 2:\n",
    "                        tem_s.add(pp)\n",
    "            for p in tem_s:\n",
    "                q.append(p)\n",
    "                visited[p] += 1\n",
    "            if (cnt % (2 * change)) >= change:\n",
    "                cnt += 2 * change - (cnt % (2 * change))\n",
    "            cnt += time\n",
    "            # print('\\n')\n",
    "            # print(cnt)\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        g = defaultdict(set)\n",
    "        for a, b in edges:\n",
    "            g[a].add(b)\n",
    "            g[b].add(a)\n",
    "        \n",
    "        visited = defaultdict(int)\n",
    "        q = deque([1])\n",
    "        visited[1] = 1\n",
    "        cnt = 0\n",
    "        while q:\n",
    "            # print(cnt, q)\n",
    "            # print(visited.items())\n",
    "            # print()\n",
    "            tem_s = set()\n",
    "            size = len(q)\n",
    "            for i in range(size):\n",
    "                p = q.popleft()\n",
    "                # print(f'({p}:{visited[p]},{cnt})', end=', ')\n",
    "                # 第二次到达终点\n",
    "                if p == n and visited[n] == 2:\n",
    "                    return cnt\n",
    "                for pp in g[p]:\n",
    "                    # print(f'({pp})', end='')\n",
    "                    if visited[pp] < 2:\n",
    "                        tem_s.add(pp)\n",
    "            for p in tem_s:\n",
    "                q.append(p)\n",
    "                visited[p] += 1\n",
    "            if (cnt % (2 * change)) >= change:\n",
    "                cnt += 2 * change - (cnt % (2 * change))\n",
    "            cnt += time\n",
    "            # print('\\n')\n",
    "            # print(cnt)\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "由于time和change是固定的，而不是在不同边有不同的值，\n",
    "所以我们可以统计出起点到终点的最短距离和次短距离，然后根据次短距离计算答案。\n",
    "'''\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        graph = defaultdict(set)\n",
    "        for a,b in edges:\n",
    "            graph[a].add(b)\n",
    "            graph[b].add(a)\n",
    "        # idx, dist\n",
    "        pq = deque([(1, 0)])\n",
    "        explored = [[inf] * 2 for _ in range(n)]\n",
    "        explored[0][0] = 0\n",
    "        while pq:\n",
    "            idx, dist = pq.popleft()\n",
    "            for other in graph[idx]:\n",
    "                if dist + 1 < explored[other - 1][0]:\n",
    "                    explored[other - 1][0] = dist + 1\n",
    "                elif explored[other - 1][0] < dist + 1 < explored[other - 1][1]:\n",
    "                    explored[other - 1][1] = dist + 1\n",
    "                    if other == n:\n",
    "                        ans = 0\n",
    "                        for i in range(explored[-1][1]):\n",
    "                            ans += time\n",
    "                            if i < explored[-1][1] - 1 and (ans // change) % 2:\n",
    "                                ans = (ans + change) // change * change\n",
    "                        return ans\n",
    "                else:\n",
    "                    continue\n",
    "                pq.append((other, dist + 1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        # 1. O(V+E) build adjacency list of undirected graph\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u-1].append((v-1, time))\n",
    "            g[v-1].append((u-1, time))\n",
    "\n",
    "        # 2. O((V+E)logV) run heap-optimized Dijkstra's algorithm\n",
    "        dist = self.bfs(0, g)\n",
    "\n",
    "        ans = 0 \n",
    "        for i in range(dist[n-1]):\n",
    "            q, r = divmod(ans, change)\n",
    "            if q % 2:\n",
    "                wait = change - r \n",
    "            else:\n",
    "                wait = 0\n",
    "            ans += time + wait \n",
    "\n",
    "        return ans \n",
    "    \n",
    "\n",
    "    def bfs(self, start: int, g: List[List[int]]) -> List[int]:\n",
    "        n = len(g)\n",
    "        dist1 = [math.inf] * n \n",
    "        dist2 = [math.inf] * n\n",
    "        dist1[start] = 0 \n",
    "        pq = [(0, start)]  # min-heap\n",
    "        while pq:\n",
    "            d, u = heapq.heappop(pq)\n",
    "    \n",
    "            for v, w in g[u]:\n",
    "                if dist1[v] > d+1:\n",
    "                    dist2[v] = dist1[v]\n",
    "                    dist1[v] = d+1\n",
    "                    heapq.heappush(pq, (dist1[v], v))\n",
    "                    heapq.heappush(pq, (dist2[v], v))\n",
    "\n",
    "                elif dist1[v] < d+1 < dist2[v]:\n",
    "                    dist2[v] = d+1 \n",
    "                    heapq.heappush(pq, (dist2[v], v))\n",
    "        return dist2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        graph = defaultdict(set)\n",
    "        for a,b in edges:\n",
    "            graph[a].add(b)\n",
    "            graph[b].add(a)\n",
    "        # idx, dist\n",
    "        pq = deque([(1, 0)])\n",
    "        explored = [[inf] * 2 for _ in range(n)]\n",
    "        explored[0][0] = 0\n",
    "        while pq:\n",
    "            idx, dist = pq.popleft()\n",
    "            for other in graph[idx]:\n",
    "                if dist + 1 < explored[other - 1][0]:\n",
    "                    explored[other - 1][0] = dist + 1\n",
    "                elif explored[other - 1][0] < dist + 1 < explored[other - 1][1]:\n",
    "                    explored[other - 1][1] = dist + 1\n",
    "                    if other == n:\n",
    "                        ans = 0\n",
    "                        for i in range(explored[-1][1]):\n",
    "                            ans += time\n",
    "                            if i < explored[-1][1] - 1 and (ans // change) % 2:\n",
    "                                ans = (ans + change) // change * change\n",
    "                        return ans\n",
    "                else:\n",
    "                    continue\n",
    "                pq.append((other, dist + 1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "from math import inf\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        graph = defaultdict(set)\n",
    "        for a,b in edges:\n",
    "            graph[a].add(b)\n",
    "            graph[b].add(a)\n",
    "        \n",
    "        # idx, dist\n",
    "        pq = deque([(1, 0)])\n",
    "        explored = [[inf] * 2 for _ in range(n)]\n",
    "        explored[0][0] = 0\n",
    "        \n",
    "        while pq:\n",
    "            idx, dist = pq.popleft()\n",
    "            for other in graph[idx]:\n",
    "                if dist + 1 < explored[other - 1][0]:\n",
    "                    explored[other - 1][0] = dist + 1\n",
    "                elif explored[other - 1][0] < dist + 1 < explored[other - 1][1]:\n",
    "                    explored[other - 1][1] = dist + 1\n",
    "                    if other == n:\n",
    "                        ans = 0\n",
    "                        for i in range(explored[-1][1]):\n",
    "                            ans += time\n",
    "                            if i < explored[-1][1] - 1 and (ans // change) % 2:\n",
    "                                ans = (ans + change) // change * change\n",
    "                        return ans\n",
    "                else:\n",
    "                    continue\n",
    "                pq.append((other, dist + 1))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        for v in edges:\n",
    "            g[v[0] - 1].append((v[1] - 1, time))\n",
    "            g[v[1] - 1].append((v[0] - 1, time))\n",
    "\n",
    "        dist = [[math.inf]*2 for _ in range(n)]\n",
    "        dist[0][0] = 0\n",
    "\n",
    "        queue = deque([(0, 0)])\n",
    "\n",
    "        while queue:\n",
    "            node, d = queue.popleft()\n",
    "            for to, w in g[node]:\n",
    "                d_temp = d\n",
    "\n",
    "                if d // change % 2 == 1:\n",
    "                    d_temp += change - (d % change)\n",
    "\n",
    "                d_temp += w\n",
    "\n",
    "                if d_temp < dist[to][0]:\n",
    "                    dist[to][0] = d_temp\n",
    "                    queue.append((to, d_temp))\n",
    "                elif d_temp > dist[to][0] and d_temp < dist[to][1]:\n",
    "                    dist[to][1] = d_temp\n",
    "                    queue.append((to, d_temp))\n",
    "\n",
    "        return dist[n - 1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        #迪杰斯特拉\n",
    "        import heapq\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            graph[edge[0] - 1].append(edge[1] - 1)\n",
    "            graph[edge[1] - 1].append(edge[0] - 1)\n",
    "\n",
    "\n",
    "        q = [(0, 0)]\n",
    "        dis = [[float(\"inf\")] * 2 for _ in range(n)]\n",
    "\n",
    "        min_time = 0\n",
    "        while q:\n",
    "            t, u = heapq.heappop(q)\n",
    "            if t < dis[u][0]:\n",
    "                dis[u][0] = t\n",
    "            elif dis[u][0] < t < dis[u][1]:\n",
    "                dis[u][1] = t\n",
    "            else:\n",
    "                continue\n",
    "            \n",
    "\n",
    "            for v in graph[u]:\n",
    "                r = t // change\n",
    "                if r % 2 == 1:\n",
    "                    t = (r + 1) * change\n",
    "                heapq.heappush(q, (t + time, v))\n",
    "        return dis[-1][1]\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        # 1. O(V+E) build adjacency list of undirected graph\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u-1].append((v-1, time))\n",
    "            g[v-1].append((u-1, time))\n",
    "\n",
    "        # 2. O((V+E)logV) run heap-optimized Dijkstra's algorithm\n",
    "        dist = self.Dijkstra(0, g, change)\n",
    "\n",
    "        return dist[n-1]\n",
    "    \n",
    "\n",
    "    def Dijkstra(self, start: int, g: List[List[int]], change: int) -> List[int]:\n",
    "\n",
    "        n = len(g)\n",
    "        dist1 = [math.inf] * n \n",
    "        dist2 = [math.inf] * n\n",
    "        dist1[start] = 0 \n",
    "        pq = [(0, start)]  # min-heap\n",
    "        while pq:\n",
    "            d, u = heapq.heappop(pq)\n",
    "    \n",
    "            for v, w in g[u]:\n",
    "                q, r = divmod(d, change)\n",
    "                if q % 2:\n",
    "                    wait = change - r \n",
    "                else:\n",
    "                    wait = 0 \n",
    "                dist = d + w + wait \n",
    "                if dist1[v] > dist:\n",
    "                    dist2[v] = dist1[v]\n",
    "                    dist1[v] = dist \n",
    "                    heapq.heappush(pq, (dist1[v], v))\n",
    "                    heapq.heappush(pq, (dist2[v], v))\n",
    "\n",
    "                elif dist1[v] < dist < dist2[v]:\n",
    "                    dist2[v] = dist \n",
    "                    heapq.heappush(pq, (dist2[v], v))\n",
    "        return dist2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            graph[u-1].append(v-1)\n",
    "            graph[v-1].append(u-1)\n",
    "\n",
    "        heap = [(0, 0)]\n",
    "        dist1, dist2 = [math.inf] * n, [math.inf] * n\n",
    "        dist1[0] = 0\n",
    "        seen = set()\n",
    "        while heap:\n",
    "            d, cur = heapq.heappop(heap)\n",
    "            if d > dist2[cur] or (d, cur) in seen:\n",
    "                continue\n",
    "            seen.add((d, cur))\n",
    "\n",
    "            if d % (change * 2) >= change:\n",
    "                d = (d // (change * 2) + 1) * (change * 2)\n",
    "            d += time\n",
    "            for nxt in graph[cur]:\n",
    "                if d < dist1[nxt]:\n",
    "                    dist1[nxt], dist2[nxt] = d, dist1[nxt]\n",
    "                    heapq.heappush(heap, (d, nxt))\n",
    "                elif dist1[nxt] < d < dist2[nxt]:\n",
    "                    dist2[nxt] = d\n",
    "                    heapq.heappush(heap, (d, nxt))\n",
    "\n",
    "        return dist2[-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
